package leetcode.primary;

import java.util.*;

public class T207 {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        if (numCourses==1){
            return true;
        }
        Set<Vertex> set = new HashSet<>();
        Vertex[] vertices = new Vertex[numCourses];
        for (int i = 0; i < numCourses; i++) {
            vertices[i] = new Vertex(i);
            set.add(vertices[i]);
        }

        for (int i = 0; i < prerequisites.length; i++) {
                vertices[prerequisites[i][1]].edge.add(prerequisites[i][0]);
                vertices[prerequisites[i][0]].inDegree+=1;
                set.remove(vertices[prerequisites[i][0]]);
        }

        System.out.println();
        for (Vertex vertex : vertices) {
            System.out.println("vertex="+vertex.number);
            System.out.println("inDegree="+vertex.inDegree);
            for (Integer integer : vertex.edge) {
                System.out.print(integer+" ");
            }
            System.out.println();
            System.out.println("-------");
        }

        int count = set.size();
        while(set.size()!=0){
            Vertex vertex = set.iterator().next();
            for (int integer : vertex.edge) {
                if (vertices[integer].inDegree>=0){
                    vertices[integer].inDegree--;
                    if (vertices[integer].inDegree==0){
                        set.add(vertices[integer]);
                        count++;
                        System.out.println("vertex1="+vertex.number + ",vertex2="+vertices[integer].number);
                        for (Vertex v : set) {
                            System.out.print("set.vertex="+v.number+" ");
                        }
                        System.out.println();
                    }
                }

            }
//            vertex.flag = true;
            set.remove(vertex);
            System.out.println("-------------");
        }
        return count == numCourses;
    }

    public void Scan(){
        Scanner scanner = new Scanner(System.in);
        for (int i = 0; i < 5; i++) {
            if (scanner.hasNextInt()){
                int value = scanner.nextInt();
            }
        }
    }

    public static void main(String[] args) {
        T207 t207 = new T207();
        t207.Scan();
        int[][] courses = {{1,4},{2,4},{3,1},{3,2}};
        boolean canFinish = t207.canFinish(5, courses);
        System.out.println(canFinish);
    }
}

class Vertex{
    int number;
    int inDegree;
    List<Integer> edge ;
    boolean flag;       //已经遍历过

    public Vertex(int number) {
        this.number = number;
        inDegree = 0;
        edge= new ArrayList<>();
        flag = false;
    }

}
